МІНІСТЕРСТВО ОСВІТИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” Інститут комп”ютерних технологій, автоматики та метрології кафедра автоматики та телемеханіки ЗВІТ ПРО ВИКОНАННЯ ЛАБОРАТОРНОЇ РОБОТИ №3 з курсу: “ Методи та засоби криптографічних перетворень ” на тему: “ Дослідження асиметричної криптосистеми RSA ”  Львів – 2006 Мета: Вивчити алгоритм RSA та навчитися зашифровувати та розшифровувати масиви даних з допомогою цього алгоритму. Завдання 1. 1.Вивчити теоретичні відомості стосовно криптосистеми RSA та загальні поняття з теорії великих чисел. 2. Скористайтесь демонстраційною програмою RSA (RSA.exe) для дослідження процесу зашифровування та розшифровування з допомогою криптосистеми RSA. 3.Зашифрувати інформацію подану у вигляді слова за алгоритмом RSA. Із таблиці 1 вибирають слово для шифрування, таблиці 3 – потрібні для реалізації цього алгоритму числа ( p q). Таблиця 2. Варіанти 1 2 3 4 5 6 7 8 9 10 11  Слово О М Д Т Ш Х Ф С Н Л Е   Д Е В Р У І О І И І Р   А Д А И М Д Н М З С А   Таблиця 3. Варіанти 1 2 3 4 5 6 7 8 9 10 11  p 3 5 7 3 5 7 3 5 7 11 11  q 17 13 11 13 11 13 11 17 17 17 13   Букви тексту замінити натуральними числами, що відповідають порядковому номеру букви в українському алфавіті, наприклад А=1, Б=2, В=3 і т.д. 4.Скласти звіт, додавши до нього результати виконання роботи по пунктах 1,2,3 та висновки по роботі. Завдання 2. 1. Написати програму, зручною для вас мовою програмування, для обчислення функції fi(xi)=xiemod p над блоками вхідної послідовності довжиною по 128 біт. У якості вхідної послідовності взяти довільний текстовий файл. При виникненні блоку з кількістю біт меншою за 128, доповнити його нулями. e – довільне велике число довжиною 128 біт; p - довільне велике просте число довжиною 128 біт. Процедуру піднесення до степеня необхідно виконати з використанням бінарного алгоритму. Операцію модульного множення чисел виконати з допомогою класичного алгоритму та алгоритму Монтгомері. Порівняти швидкодії обчислення лишків для цих двох алгоритмів. Оцінити загальну швидкодію обчислень. 2. Результати виконання програми записати у файл даних. 3.Скласти звіт, додавши до нього результати виконання роботи та висновки по роботі. Теоретичні відомості Генерування ключів. Вибирають два досить великі прості числа
. Для їх добутку
значення функції Ойлера дорівнює
. Далі випадковим чином вибирають елемент
, що не перевищує значення
і взаємно простий з ним. Іншими словами,
є випадковим елементом із множини
. Для
за алгоритмом Евкліда знаходять елемент
, обернений до
в
, тобто такий, що
і
. Як результат покладають: Відкритий ключ:
Таємний ключ:
. Шифрування відбувається блоками. Для цього повідомлення записують у цифровій формі і розбивають на блоки так, що кожен блок позначає число, яке не перевищує
. Якщо блок записаний у вигляді двійкового слова довжини
, то повинна виконуватись нерівність
. Блок
розглядається як елемент кільця
і як такий, може підноситись до степеня за модулем
. Алгоритм шифрування
у системі
полягає у піднесені
до степеня
. Записується це так:
Результат роботи тестової програми This program implements the simulation of R S A system ----------------------------- Input text = theformatofthesefilesissequenceofenriesEntriesarepredonantlylineorientedthosparenthesescanbeusedtocontinuealistofitemsthatacrosslineboundary Input text length = 140 random P = 151 random Q = 67 N = 10117 Phi(N)= 9900 generated E = 7 public key (E,N) = (7,10117) generated D = 4243 private(secret) key (D,N) = (4243,10117) E N C R Y P T I O N cipher text = (plain text)** E (mod N) plain cipher t 116 - 3054 h 104 - 8144 e 101 - 815 f 102 - 4560 o 111 - 2328 r 114 - 8602 m 109 - 2671 a 97 - 5926 t 116 - 3054 o 111 - 2328 f 102 - 4560 t 116 - 3054 h 104 - 8144 e 101 - 815 s 115 - 3602 e 101 - 815...